# -*- coding: utf-8 -*-

"""516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成"""

class Solution:
    """
    最长的子序列要是回文，那就给一个倒序的序列，然后求这两个字符串的最长公共子序列。然后就转换为矩阵的算法。
        b b b a b
    b   1 1 1 0 1
    a   0 0 0 1 0
    b   1 1 1 0 1
    b   1 1 1 0 1
    b   1 1 1 0 1

    直接用递推还要方便些，因为下一步可以怎么走取决于当前位置是否为1。
    定义 dp[i][j] 为从首行到达 (i,j) 位置的路径上经过的最大和。
    若(i,j) = 1, 可以往右下方走一步；若 (i,j) = 0, 可以往右或者往下走一步。
    递推状态转移：
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+common[i+1][j+1])     # 当 common[i][j] = 1
        dp[i][j+1] = max(dp[i][j+1], dp[i][j]+common[i][j+1])           # 当 common[i][j] = 0
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+common[i+1][j])           # 当 common[i][j] = 0
    递推基础：
        dp[0][j] = common[0][j]
    """
    def longestPalindromeSubseq(self, s: str) -> int:
        r = ''.join(reversed(s))
        s, r = s+'1', r+'2'
        d = len(s)
        common = [[int(s[i]==r[j]) for j in range(d)] for i in range(d)]
        dp = [[0 for _ in range(d)] for _ in range(d)]

        j = 0
        while j < d:
            dp[0][j] = common[0][j]
            j += 1

        longest = 0

        i = 0
        while i < d-1:
            j = 0
            while j < d-1:
                longest = max(longest, dp[i][j])
                if common[i][j]:
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+common[i+1][j+1])
                else:
                    dp[i][j+1] = max(dp[i][j+1], dp[i][j]+common[i][j+1])
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j]+common[i+1][j])
                j += 1
            i += 1

        # for bar in dp:
        #     print(bar)

        return longest

if __name__ == '__main__':
    rs = Solution().longestPalindromeSubseq("bbbab")
    print(rs)
